package xiaolong.arithmetic.fun_lib;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * Created by xiaolong on 2020/8/2 3:19 PM
 * email：xinxiaolong123@foxmail.com
 *
 *
 * <p>
 * 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
 * <p>
 * J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
 * <p>
 * 示例 1:
 * <p>
 * 输入: J = "aA", S = "aAAbbbb"
 * 输出: 3
 * 示例 2:
 * <p>
 * 输入: J = "z", S = "ZZ"
 * 输出: 0
 *
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jewels-and-stones
 *
 *
 */
public class GemsAndStones {

    public static void main(String[] agr) {

        GemsAndStones gemsAndStones = new GemsAndStones();
        int gemNums=gemsAndStones.numJewelsInStones4("aA", "aAAbbbb");
        System.out.println("宝石数量："+gemNums);
    }


    /**
     * 8 ms , 在所有 Java 提交中击败了 5.25% 的用户
     *
     * 本以为直接用map进行查找会很快，没想到结果只击败了5.25%的用户。
     * 因为map的开销大了些吧。看看其他的答案呢
     *
     * @param J
     * @param S
     * @return
     */
    public int numJewelsInStones(String J, String S) {

        if (J == null || J.isEmpty() || S == null || S.isEmpty()) {
            return 0;
        }

        String[] gems = J.split("");
        String[] stones = S.split("");
        HashMap<String, Integer> map = new HashMap<>();

        //将石头集合转换成map。用value为int类型标示出现的次数。
        for (String stone : stones) {

            Integer num = map.get(stone);

            if (num == null) {
                map.put(stone, new Integer(1));
            } else {
                map.put(stone, ++num);
            }
        }

        int gemsNum=0;

        for (int i = 0; i < gems.length; i++) {
            String gem = gems[i];
            Integer num = map.get(gem);

            //当查找到时，将出现的次数赋值给gemsNum
            if(num!=null&&num>0){
                gemsNum=gemsNum+num;
            }
        }

        return gemsNum;
    }

    /**
     *
     * 2 ms, 在所有 Java 提交中击败了 47.34% 的用户
     *
     * 官方思路，使用set，不必保存出现次数。
     * 将宝石进行set保存。也是一种巧妙思路
     *
     * 快了4倍，但是还是不够快。还有更快的？！
     *
     * 快在哪里呢？我将数组改为Character试试，是不是在转数组的时候耗时了。
     *
     */
    public int numJewelsInStones2(String J, String S) {

        Set<Character> gSet=new HashSet<>();
        for (Character c:J.toCharArray()) {
            gSet.add(c);
        }

        int gemsNum=0;


        for (Character s:S.toCharArray()){
            if(gSet.contains(s)){
                gemsNum++;
            }
        }
        return gemsNum;
    }


    /**
     *2 ms , 在所有 Java 提交中击败了 47.34% 的用户
     * @param J
     * @param S
     * @return
     *
     * 这下速度上来了，看来是跟转数组有关系。因为两者都用的hash进行存储。都涉及到hash算法等，差异不是很大
     * 唯一明显的差距就是转数组。这里直接转toCharArray。看来toCharArray性能真的够好。
     */
    public int numJewelsInStones3(String J, String S) {

        if (J == null || J.isEmpty() || S == null || S.isEmpty()) {
            return 0;
        }

        HashMap<Character, Integer> map = new HashMap<>();

        //将石头集合转换成map。用value为int类型标示出现的次数。
        for (Character stone : S.toCharArray()) {

            Integer num = map.get(stone);

            if (num == null) {
                map.put(stone, new Integer(1));
            } else {
                map.put(stone, ++num);
            }
        }

        int gemsNum=0;

        for (Character g:J.toCharArray()){
            Integer num = map.get(g);
            //当查找到时，将出现的次数赋值给gemsNum
            if(num!=null&&num>0){
                gemsNum=gemsNum+num;
            }
        }

        return gemsNum;
    }




    /**
     *2 ms , 在所有 Java 提交中击败了 47.34% 的用户
     * @param J
     * @param S
     * @return
     *
     * charAt 性能变化不大，性能影响还在于 hash算法。
     *
     * 因为数据量不大：S 和 J 最多含有50个字母。
     * 暴力两个for进行比对是最快的。
     * 
     */
    public int numJewelsInStones4(String J, String S) {

        if (J == null || J.isEmpty() || S == null || S.isEmpty()) {
            return 0;
        }

        HashMap<Character, Integer> map = new HashMap<>();

        //将石头集合转换成map。用value为int类型标示出现的次数。
        for (int i=0;i<S.length();i++) {

            Character s=S.charAt(i);
            Integer num = map.get(s);

            if (num == null) {
                map.put(s, new Integer(1));
            } else {
                map.put(s, ++num);
            }
        }

        int gemsNum=0;


        for (int i=0;i<J.length();i++){
            Integer num = map.get(J.charAt(i));
            //当查找到时，将出现的次数赋值给gemsNum
            if(num!=null&&num>0){
                gemsNum=gemsNum+num;
            }
        }

        return gemsNum;
    }

}
